#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>

using namespace std;

class MedianFinder {
public:
    priority_queue<double> heap1;
    priority_queue<double, vector<double>, greater<double>> heap2;
    MedianFinder() {

    }

    void addNum(int num) {
        if (heap1.size() == heap2.size())
        {
            if (heap1.empty() || heap1.top() >= num)
            {
                heap1.push(num);
            }
            else
            {
                heap2.push(num);
                int y = heap2.top();
                heap2.pop();
                heap1.push(y);
            }
        }
        else
        {
            if (num <= heap1.top())
            {
                heap1.push(num);
                int x = heap1.top();
                heap1.pop();
                heap2.push(x);
            }
            else
            {
                heap2.push(num);
            }
        }
    }

    double findMedian() {
        if (heap1.size() == heap2.size())
        {
            double x = heap1.top();

            double y = heap2.top();

            return (x + y) / 2;
        }
        else
        {
            double x = heap1.top();
            return x;
        }
    }
};

int main()
{

	return 0;
}